<?php
/*
 * 给定一个整数矩阵matrix，每个位置你可以向左、右、下、上移动，找到其中最长的递增路径。
 * 例如：matrix =
 * [
 *   [9,9,4],
 *   [6,6,8],
 *   [2,1,1]
 * ]
 * 返回4
 * 最长路径是[1, 2, 6, 9].
 */

$matrix = [
    [9, 9, 4],
    [6, 6, 8],
    [2, 1, 1],
];
$obj    = new Code_03_LongestIncreasingPath();
var_dump($obj->do1($matrix));
var_dump($obj->do2($matrix));

class Code_03_LongestIncreasingPath
{
    // 递归
    public function do1($matrix)
    {
        $max = PHP_INT_MIN;
        for ($row = 0, $rowLen = count($matrix); $row < $rowLen; $row++) {
            for ($col = 0, $colLen = count($matrix[0]); $col < $colLen; $col++) {
                $max = max($max, $this->process($matrix, $row, $col));
            }
        }
        return $max;
    }

    public function process($matrix, $row, $col)
    {
        $path = 1;  //原地不动的长度
        if ($col > 0 && $matrix[$row][$col - 1] > $matrix[$row][$col]) {
            $path = max($path, $this->process($matrix, $row, $col - 1) + 1);
        }
        if ($row > 0 && $matrix[$row - 1][$col] > $matrix[$row][$col]) {
            $path = max($path, $this->process($matrix, $row - 1, $col) + 1);
        }
        if ($row < count($matrix) - 1 && $matrix[$row + 1][$col] > $matrix[$row][$col]) {
            $path = max($path, $this->process($matrix, $row + 1, $col) + 1);
        }
        if ($col < count($matrix[0]) - 1 && $matrix[$row][$col + 1] > $matrix[$row][$col]) {
            $path = max($path, $this->process($matrix, $row, $col + 1) + 1);
        }
        return $path;
    }

    // DP
    public function do2($matrix)
    {
        $rowLen = count($matrix);
        $colLen = count($matrix[0]);
        $dp     = array_fill(0, $rowLen, array_fill(0, $colLen, 0));
        $max    = 0;
        for ($row = 0, $rowLen = count($matrix); $row < $rowLen; $row++) {
            for ($col = 0, $colLen = count($matrix[0]); $col < $colLen; $col++) {
                $max = max($max, $this->maxIncrease($matrix, $dp, $row + 1, $col, $matrix[$row][$col]) + 1);
                $max = max($max, $this->maxIncrease($matrix, $dp, $row, $col + 1, $matrix[$row][$col]) + 1);
                $max = max($max, $this->maxIncrease($matrix, $dp, $row - 1, $col, $matrix[$row][$col]) + 1);
                $max = max($max, $this->maxIncrease($matrix, $dp, $row, $col - 1, $matrix[$row][$col]) + 1);
            }
        }
        return $max;
    }

    public function maxIncrease($matrix, $dp, $row, $col, $pre)
    {
        if ($row < 0 || $row >= count($matrix) || $col < 0 || $col >= count($matrix[0]) || $matrix[$row][$col] >= $pre) {
            return 0;
        }
        if ($dp[$row][$col] == 0) {
            $dp[$row][$col] = $this->maxIncrease($matrix, $dp, $row + 1, $col, $matrix[$row][$col]) + 1;
            $dp[$row][$col] = max($dp[$row][$col], $this->maxIncrease($matrix, $dp, $row, $col + 1, $matrix[$row][$col]) + 1);
            $dp[$row][$col] = max($dp[$row][$col], $this->maxIncrease($matrix, $dp, $row - 1, $col, $matrix[$row][$col]) + 1);
            $dp[$row][$col] = max($dp[$row][$col], $this->maxIncrease($matrix, $dp, $row, $col - 1, $matrix[$row][$col]) + 1);
        }

        return $dp[$row][$col];
    }


}